102. Экологическая упаковка бутылок
Имеются три тары, в каждой
из которых находятся бутылки трех типов: коричневые, зеленые и прозрачные.
Необходимо переложить наименьшее количество бутылок из одних тар в другие так,
чтобы в каждой таре находились бутылки одного вида.
Вход. Каждая строка является отдельным тестом и содержит 9
целых чисел. Первые три числа характеризуют количество коричневых (‘B’), зеленых
(‘G’) и прозрачных (‘C’) бутылок в таре
номер 1, следующие три числа – соответственно количество таких же бутылок в
таре номер 2, и последние три числа – соответственно содержимое тары номер 3.
Выход. Для
каждого теста вывести оптимальную конфигурацию – три буквы из множества {‘B’,’G’,’C’},
характеризующие содержимое первой, второй и третьей тары после оптимальной
сортировки бутылок, а также наименьшее количество их перекладываний. Если
оптимальных конфигураций несколько, то вывести лексикографически наименьшую.
1 2 3 4 5 6
7 8 9
5 10 5 20
10 5 10 20 10
BCG 30
CBG 50
комбинаторика
Имеются три типа бутылок и
три тары. В каждую тару следует переместить бутылки одного типа. Переберем все
возможные перестановки из трех элементов, стараясь разные типы бутылок
расположить в разные тары. Всего получится 3! = 6 конфигураций. Каждая
конфигурация характеризуется тремя буквами. Например, конфигурация BCG означает, что коричневые бутылки собираем
в первой таре, прозрачные во второй, зеленые в третьей. Для каждой конфигурации
подсчитываем число перемещаемых бутылок и ищем ту, для которой это значение
будет наименьшим. Конфигурации бутылок следует перебирать от лексикографически наименьшей
BCG до лексикографически наибольшей GCB.
Первый тест содержит
следующую информацию:
|
тип бутылки / номер тары |
1 |
2 |
3 |
сумма |
|
коричневая |
1 |
4 |
7 |
12 |
|
зеленая |
2 |
5 |
8 |
15 |
|
прозрачная |
3 |
6 |
9 |
18 |
Оптимальной будет конфигурация BCG. Для перемещения всех коричневых бутылок
в первую тару надо совершить 4 + 7 = 11 (или 12 – 1) перемещений, зеленых во
вторую тару 2 + 8 = 10 перемещений, прозрачных в третью тару 3 + 6 = 9
перемещений. Итого следует совершить 11 + 10 + 9 = 30 перемещений.
Информацию о бутылках в таре i храним в массиве bin[i],
i = 1, 2, 3. Данные о коричневых
бутылках храним в bin[i][0], о
прозрачных в bin[i][1], о зеленых в
bin[i][2].В ячейке sum[i] будем подсчитывать количество коричневых (‘B’), прозрачных (‘C’) и зеленых (‘G’) бутылок
соответственно. Типы бутылок расположены именно в такой последовательности, так
как конфигурация “BCG” является лексикографически наименьшей. В массиве a будут
генерироваться перестановки чисел от {0, 1, 2} до {2, 1, 0}, массив b будет
хранить оптимальную перестановку.
int sum[3], bin[3][3];
int summa, best, i, j;
vector<int> a(3,0), b(3,0);
Читаем входные данные в массив bin.
while(scanf("%d
%d %d %d %d %d %d %d %d",&bin[0][0],&bin[0][2],&bin[0][1],
&bin[1][0],&bin[1][2],&bin[1][1],
&bin[2][0],&bin[2][2],&bin[2][1]) == 9)
{
Вычисляем количество коричневых, прозрачных и зеленых бутылок.
for(i = 0; i
< 3; i++) sum[i] = bin[i][0] + bin[i][1] + bin[i][2];
В переменной best
храним искомое оптимальное количество перемещений бутылок. Инициализируем
массив a = {0, 1, 2}.
best = 2000000000; for(i
= 0; i < 3; i++) a[i] = i;
В массиве a перебираем все перестановки чисел от 0 до
2. Числам 0, 1, 2 соответствуют бутылки типов ‘B’, ‘C’ и ‘G’. Для каждой
перестановки подсчитываем количество перекладываемых бутылок и сравниваем его
со значением best. Каждый раз найденную лучшую конфигурацию запоминаем в
массиве b.
do {
summa = 0;
for(i = 0; i < 3; i++) summa += sum[i] -
bin[i][a[i]];
if (summa < best) best = summa, b = a;
} while(next_permutation(a.begin(),a.end()));
Выводим оптимальную конфигурацию, хранящуюся в массиве
b и количество перемещений бутылок best.
for(i = 0; i < 3; i++)
if (b[i] == 0) printf("B");
else
if (b[i] == 1) printf("C");
else printf("G");
printf(" %d\n",best);
}